package practise;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    public List<List<Integer>> levelOrder1(TreeNode root) {
        //外部用 ArrayList 内部用 ListedLink 因为外部当深度变大的时候要频繁访问 内部是要频繁尾插
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        //存放层序遍历的循序
        Queue<TreeNode> queue = new LinkedList<>();

        ret.add(new LinkedList<>());
        int cur = 1;//当前这一层的元素个数
        int next = 0;//下一层的元素个数
        int index = 0;//深度
        queue.add(root);
        while(!queue.isEmpty()) {
            //获取一个节点
            TreeNode poll = queue.poll();
            //先判断当前节点是否已经结束
            if(cur == 0) {//已经结束 就要创建一个新的 LinkedList
                ret.add(new LinkedList<>());
                cur = next;
                index++;
                next = 0;
            }
            //创建完后还要 添加
            ret.get(index).add(poll.val);
            cur--;
            if(poll.left != null) {
                next++;
                queue.add(poll.left);
            }
            if(poll.right != null) {
                next++;
                queue.add(poll.right);
            }
        }
        return ret;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        //外部用 ArrayList 内部用 ListedLink 因为外部当深度变大的时候要频繁访问 内部是要频繁尾插
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        //存放层序遍历的循序
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();//得到当前这一层的元素个数，然后遍历
            List<Integer> tmp = new LinkedList<>();//这个是一层的元素
            while(size-- != 0) {
                TreeNode poll = queue.poll();
                tmp.add(poll.val);
                if(poll.left != null) {
                    queue.add(poll.left);
                }
                if(poll.right != null) {
                    queue.add(poll.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
}
